import java.util.Arrays;
import java.util.Scanner;

class Main
    {
        /**
         * NC213471 爱丽丝人偶
         *https://ac.nowcoder.com/acm/problem/213471
         */
        public static void main1(String[] args){
            Scanner in = new Scanner(System.in);

            int n = in.nextInt();
            int left = 1,right = n;

            while(left < right)
            {
                System.out.print(left + " " );
                System.out.print(right + " ");
                left++;right--;
            }
            if(left == right) System.out.print(left);
        }
        /**
         * JD7 合并数组，并升序
         *https://www.nowcoder.com/practice/635ff765d4af45b5bf8e3756ed415792?tpId=134&tqId=33860&ru=/exam/oj
         * @param args
         */
        public static void main2(String[] args)
        {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt(),m = in.nextInt();

            int[] A = new int[n];
            int[] B = new int[m];

            for(int i = 0;i < n;i++) A[i] = in.nextInt();
            for(int j = 0;j < m;j++) B[j] = in.nextInt();

            Arrays.sort(A);
            Arrays.sort(B);

            int[] C = new int[n + m];

            int s1 = 0,s2 = 0,k = 0;
            while(s1 < n && s2 < m)
            {
                if(A[s1] > B[s2])
                {
                    C[k++] = B[s2++];
                }
                else if(A[s1] < B[s2])
                {
                    C[k++] = A[s1++];
                }
                else s1++;
            }

            while(s1 < n) C[k++] = A[s1++];
            while(s2 < m) C[k++] = B[s2++];

            for(int i = 0;i < k;i++) System.out.print(C[i] + " ");

        }
        /**
         * dp22 最长回文子序列
         * https://www.nowcoder.com/practice/82297b13eebe4a0981dbfa53dfb181fa?tpId=230&tqId=39762&ru=/exam/oj
         * @param args
         */
        public static void main3(String[] args)
        {
            Scanner in = new Scanner(System.in);
            char[] ch = in.nextLine().toCharArray();

            int n = ch.length;

            int[][] dp = new int[n][n];

            for(int i = n - 1;i >= 0;i--)
            {
                dp[i][i] = 1;
                for(int j = i + 1;j < n;j++)
                {
                    if(ch[i] == ch[j])
                    {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                    else
                    {
                        dp[i][j] = Math.max(dp[i][j -1],dp[i + 1][j]);
                    }
                }
            }

            System.out.println(dp[0][n - 1]);

        }
    }

